/* 
* Authors: Stefan Bojarovski <bojarovski@gmail.com>
*		   Dmitry Lebedev <leeevd@gmail.com>
* June,	2011
*/

#include "max_clique.h"
#include "simple_bt.h"

using namespace boost;

simple_bt::simple_bt(Graph * const g)
{
	inGraph = g;
	numNodes = boost::num_vertices(*inGraph);
}

VertexSet & simple_bt::get_maxClique() {
	return maxClique;
}

int simple_bt::get_num_of_nodes() const
{
	return numNodes;
}

void simple_bt::do_simple_BT()
{
	VertexSet * empty = new VertexSet;
	do_clique_BT(empty, 0, numNodes);
	delete empty;
	return;
}

/* 
* Return a set of candidates, Sq, for q-clique. Each candidate is a vector
* in which a newly added vertex must be greater than the last vertex in the 
* given vector, A, and must be connected to all vertices in A. Note that the
* returning candidate vectors are extended from the given vector A by adding
* only one additional vertex each time this method is called. 
*/

void simple_bt::get_candidates(VertexSet* A, ArrayList * setAllCandidates) 
{
	// The set of all candidate vectors for q-clique
	//ArrayList candidates;

	// If A is empty, let setCandidates be a vector with each single node in the graph
	if (A -> empty()) 
	{
		for (int i = 0; i < numNodes; i++) 
		{
			VertexSet* setCandidatesPoint = new VertexSet;
			setCandidatesPoint -> push_back(i);
			setAllCandidates -> push_back(setCandidatesPoint);
		}
	}      
	else 
	{
		// Permutate all candidate vectors, satisfying the property of setCandidates
		for (int j = A -> back() + 1; j < numNodes; j++) 
		{
			bool allConnected = true;
			// Check if j is connected to all vertices in A
			for (unsigned i = 0; i < A -> size(); i++)
			{
				Edge ed;
				bool found = false;
				tie(ed, found) = edge(j, A -> at(i), *inGraph);

				if (!found)
				{
					allConnected = false;
					break;
				}
			}
			if (allConnected) {
				VertexSet* setCandidatesPoint = new VertexSet;
				setCandidatesPoint -> insert(setCandidatesPoint -> begin(), A -> begin(), A -> end());
				setCandidatesPoint -> push_back(j);
				setAllCandidates -> push_back(setCandidatesPoint);
			}        
		}
	}
	//*setAllCandidates = candidates;
}
/*
* Using recursive DFS, find k-cliques in a graph. Store only the first found
* k-clique whereas it counts the number of all k-cliques in a graph.  
*/
void simple_bt::do_clique_BT(VertexSet* A, int j, int const maxSizeClique)
{
	// setAllCandidates is the set of all candidate vectors for j-clique
	ArrayList *setAllCandidates = new ArrayList;

	get_candidates(A, setAllCandidates);
	// If j is equal to maxSizeClique, or setAllCandidates is empty, then A is maximal clique in the graph
	if (j == maxSizeClique || setAllCandidates -> empty()) 
	{
		if(A -> size() > simple_bt::maxClique.size())
		{
			maxClique.clear();
			maxClique.insert(maxClique.begin(), A -> begin(), A -> end());
		}
		for (unsigned i = 0; i < setAllCandidates -> size(); i++)
		{
			delete setAllCandidates -> at(i);
		}
		delete setAllCandidates;
		return;
	}
	else 
	{
		j++; 
		// For each candidate vector in setAllCandidates, recursively do backtracking for k-clique
		for (unsigned i = 0; i < setAllCandidates -> size(); i++)
		{
			VertexSet* aPoint = new VertexSet;
			aPoint -> insert(aPoint -> begin(), setAllCandidates -> at(i) -> begin(), setAllCandidates -> at(i) -> end());
			do_clique_BT(aPoint, j, maxSizeClique);
			//release data upon return
			delete aPoint;
		}
		for (unsigned i = 0; i < setAllCandidates -> size(); i++)
		{
			delete setAllCandidates -> at(i);
		}
		delete setAllCandidates;
	}
}


